Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Інститут дистанційного навчання
Кафедра СКС
КУРСОВА РОБОТА
з дисципліни «Програмування»
на тему «Алгоритми та структури даних»
Варіант № 8
Завдання на курсову роботу:
На вході задано масив з N елементів. Використовуючи метод бінарного пошуку знайти заданий елемент і вивести його на екран.
1.1 Ручний ввід даних.
1.2. Ввід даних через файл.
Складіть алгоритм визначення того, що бінарне дерево є:
а) строго бінарне;
б) повне;
г) майже повне.
2.1. Ручний ввід даних.
2.2. Ввід даних через файл.
ЗМІСТ
ВСТУП……………………………………………………………………….
4
1.
ТЕОРЕТИЧНА ЧАСТИНА…………………………………………..
6
1.1
Задача на пошук (Бінарний пошук або пошук діленням на половину)………………………………………………………………..
6
1.2
Задача на бінарне дерево……………………………………………….
6
2.
ОПИС АЛГОРИТМУ………………………………………………….
8
2.1
Схема алгоритму бінарного пошуку………………………………….
8
2.2
Схема алгоритму бінарного дерева……………………………………
10
3.
БЛОК-СХЕМА АЛГОРИТМУ………………………………………
11
4.
РЕЗУЛЬТАТИ ТЕСТУВАННЯ………………………………………
12
4.1
Задача на бінарний пошук………………………………………………
12
5.
ПРАКТИЧНА РЕАЛІЗАЦІЯ ПРОСТИХ МЕТОДІВ СОРТУВАННЯ…………………………………………………………
12
ВИСНОВКИ…………………………………………………………………..
20
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ……………………………..
21
Додаток…………………………………………………………………………
22
ВСТУП
Однією з найпоширеніших мов програмування є мова Pascal. Сучасні її підмножини (останні версії), а також середовище Delphi, що грунтується на мові програмування Object Pascal, широко використовують поряд з мовами С, С++, С++Builder. Вони дають змогу створювати складні програмні продукти, як у галузі системного, так і прикладного програмування. Та все ж незамінною залишається мова програмування Pascal, як інструмент для вивчення основ програмування.
На початкових етапах не було конкретних теоретичних концепцій та технологій програмування. Результат створення програм залежав, головне, від мистецтва програміста й ефективності застосованих ним хитрощів. Такі програми важко налагоджувати, вони мало придатні для вдосконалення. Особливо важко компонувати складні програми з частин, розроблених колективом програмістів.
Як уже зазначено, методологією сучасного програмування є програмування структурне. Дехто вважає, що це просто програмування згідно з чіткими канонами, інші – що це написання підпрограм (модулів) та об’єднання їх у програму, ще інші – що це програмування “без goto ”.
Мета структурного програмування – створювати програми чіткої структури, тобто такі, які можна було б без великих затрат розуміти, супроводжувати і модифікувати без участі авторів.
До структури даних відносяться: список, стек, черга, а також дерева.
Список – це скінченна сукупність даних одного типу, між якими налагоджено зв’язок. Елемент списку складається з двох частин: самого даного (даних) та вказівника на наступний елемент списку.
Стек – це структура даних, у якій елемент, записаний останнім, зчитують (є доступний до опрацювання) першим. Тут виконується принцип “останній прийшов - перший вийшов”.
Черга – це структура даних, у якій елемент, записаний першим, зчитують першим. Тут діє принцип “перший прийшов – перший вийшов”.
Дерево – це не порожня множина елементів, один з яких називається коренем, а решта поділяється на декілька підмножин, що не перетинаються.
На відмінно від структур даних, алгоритм повинен відповідати чітко вираженим діям, а також відповідати певним властивостям.
Алгоритм – це строга і чітка система правил, яка визначає послідовність дій над деякими об’єктами і після скінченого числа кроків приводить до досягнення поставленої мети.
Крім того, що алгоритм - не просто звід кінцевого числа правил, що задають послідовність виконання операцій при рішенні тієї чи іншої специфічної задачі, він має ще п'ять важливих особливостей:
Кінцевість. Алгоритм завжди повинен закінчуватись після кінцевого числа кроків.
Резул...
